#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* m2(ListNode* list1, ListNode* list2){
        if(!list1) return list2;
        if(!list2) return list1;
        if(list1->val < list2->val){
            list1->next = m2(list1->next, list2);
            return list1;
        }else{
            list2->next = m2(list2->next, list1);
            return list2;
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        if(k%2){
            vector<ListNode*> ll;
            ll.push_back(lists[k-1]);
            for(int i=0;i<k;i+=2) ll.push_back(m2(lists[i], lists[i+1]));
            return mergeKLists(ll);
        }else{
            vector<ListNode*> ll;
            for(int i=0;i<k;i+=2) ll.push_back(m2(lists[i], lists[i+1]));
            return mergeKLists(ll);
        }
    }